1. Field of the Invention
This invention relates in general to a method and apparatus for performing rotational position queue sorting without rotational position sense, and more particularly, to a method and apparatus for reordering commands in a rotational position queue based upon the relative positional relationship of the queued commands to a command assigned as the first command.
2. Description of Related Art
The reduction in the data retrieval time is a problem in the field of data storage systems. Further, a CPU central processing unit may generate so many disk drive commands within a small time interval that the commands cannot all be serviced immediately. This is especially true when the CPU is operating in a multi-tasking, multi-programming environment.
To address this problem and to minimize data retrieval times, sophisticated controllers have been developed to reorder the requests in a queue. For example, in OS/2 versions 1.0, 1.1, and 1.2, commands to a disk drive were ordered in an "elevator" sequence in which the commands are arranged in an associated service queue in a positional sequence designed to allow servicing of all enqueued requests having targeted storage locations reachable while the head of the disk drive is continuing in its present direction of motion. Other methods have focused on servicing the command which involves the smallest distance of head movement without regard to direction.
U.S. Pat. No. 5,313,585, issued May 17, 1994, to Jeffries et al., entitled "DISK DRIVE ARRAY WITH REQUEST FRAGMENTATION", incorporated herein by reference, discloses a method for performing multiple write operations within the smallest distance of head movement and lessened rotational latency. The disk drive includes a queue for access requests and each request is identified by its associated handle within a disk drive control system. Nevertheless, the disk drive manages requests serially and completes a request prior to starting the next request.
U.S. Pat. No. 5,220,653, issued Jun. 15, 1993, to Miro, entitled "SCHEDULING INPUT/OUTPUT OPERATIONS IN MULTITASKING SYSTEMS", incorporated herein by reference, discloses a method for performing multiple write operations on the basis of relative priority of tasks. The disk drive maintains a set of holding queues and an associated service queue for each physical drive in the system. Nevertheless, the commands in the services queue are serviced on a FIFO basis.
U.S. Pat. No. 5,239,640, issued Aug. 24, 1993, to Froemke et al., entitled "DATA STORAGE SYSTEM AND METHOD INCLUDING DATA AND CHECKSUM WRITE STAGING STORAGE", incorporated herein by reference, discloses an outboard data storage system for a data processing system including a plurality of data DASD's and a dedicated checksum DASD. The controller blocks data with contiguous addresses into single write commands and queues the write commands in an order corresponding to physical DASD addresses. However, this system is directed to providing a large write staging area on the order of 8 megabytes to streamline data throughput rather than to data queuing techniques.
U.S. Pat. No. 4,583,166, issued Apr. 15, 1986, to Hartung et al., entitled "ROLL MODE FOR CACHED DATA STORAGE", incorporated herein by reference, discloses creating a set of chained commands for accessing record areas to provide more rapid accessing a plurality of records. The command within the chain, irrespective of its location, having the closest logical rotational proximity to the instant rotational position of the surfaces is selected as the first command in the chain. The chain is executed beginning at the indicated rotational position selected command through the end of the chain and then wrapped to the beginning of the original chain and continuing on until the command immediately preceding the rotational position selected command has been executed. Nevertheless, the rotational position of the surfaces must first be determined. Further, the method is limited to accessing the records on a given cylinder of tracks. Further, more recent commands are not entered into the chain and therefore must wait until the processing of the chain is complete.
In summary, the reordering of commands based on rotational position has previously required first ascertaining the rotational position of the disk surfaces. However, this has posed a problem since the position of the surface changes while the position is being calculated. Further, in some drives, the calculation or estimation of the rotational position of the disk surfaces is not possible.
Therefore, it can be seen that there is a need for a method and apparatus for sorting rotational positional queues without first determining the position of the surface or surfaces.
It can also be seen that there is a need for a method and apparatus for sorting rotational positional queues that is not limited to record areas within a given track or within a given cylinder of tracks.
Finally, it can also be seen that there is a need for a method and apparatus for sorting rotational positional queues on a continual basis therefore integrating more recently received commands into the queue.